     package ronin.scene;

     import java.awt.*;
     import java.awt.geom.*;
     import java.util.*;

     import ronin.actor2d.*;

     // represents a single node within a QuadTree structure
     public class QuadNode extends Object
     {
     	int i;
     	
          // the next unique id to assign a node
          protected static int UNIQUE_ID = 0;

          // a unique integer to identify this node
          protected int id;

          // the parent that contains this node
          protected QuadNode parent;

          // an array of child nodes for this QuadNode
          protected QuadNode[] nodes;

          // true if this node is a leaf node (has no children)
          protected boolean leaf;

          // a linked-list of objects this node contains
          protected LinkedList<Moveable> objects;

          // the bounds of the node
          protected Rectangle2D bounds;
          
          public Rectangle2D viewable;

          // default constructor
          private QuadNode()
          {
               id = -1;
               parent  = null;
               nodes   = null;
               leaf    = true;
               objects = null;
               bounds  = null;
          }

          // constructs a QuadNode with the given parent, depth, and bounds
          public QuadNode(QuadNode p, int depth, Rectangle2D r, Rectangle2D v)
          {
               parent = p;
               bounds = r;
				viewable = v;
				
               id = UNIQUE_ID++;

               // this node is a leaf if the remaining depth is zero
               if(depth == 0)
               {
                    leaf = true;
                    objects = new LinkedList<Moveable>();
                    nodes = null;

                    QuadTree.addLeaf(this);
               }

               // otherwise, this node contains 4 child nodes                
               else
               {
                    leaf = false;
                    objects = null;

                    nodes = new QuadNode[4];
                    double x = bounds.getX();
                    double y = bounds.getY();
                    double w = bounds.getWidth();
                    double h = bounds.getHeight();

                    // create the children
                    nodes[0] = new QuadNode(this, depth - 1, new Rectangle2D.Double(x,       y + h/2, w/2, h/2), viewable);
                    nodes[1] = new QuadNode(this, depth - 1, new Rectangle2D.Double(x + w/2, y + h/2, w/2, h/2), viewable);
                    nodes[2] = new QuadNode(this, depth - 1, new Rectangle2D.Double(x + w/2, y      , w/2, h/2), viewable);
                    nodes[3] = new QuadNode(this, depth - 1, new Rectangle2D.Double(x,       y,       w/2, h/2), viewable);
               }
          }

          // returns true if this node is a leaf node
          public final boolean isLeaf()
          {
               return leaf;
          }

          // attempts to insert the sent object into this node
          public void insert(
               Moveable c,       // the Moveable object to insert
               boolean propagate // if true, propogate upward if c does not fit within this node's bounds
               )
          {
               // try to insert the node
               if(bounds.contains(c.getBounds()) || bounds.intersects(c.getBounds()))
               {
                    // if this node is a leaf node, insert the object into the list
                    if(isLeaf())
                    {
                         if(objects == null)
                         {
                              objects = new LinkedList<Moveable>(); 
                         }
                         if(! objects.contains(c))
                         {
                              objects.add(c);
                         }
                    }

                    // if this node is not a leaf, try to insert downward
                    else
                    {
                         for(i = 0; i < 4; i++)
                         {
                              if(nodes[i] != null)
                              {
                                   nodes[i].insert(c, false);
                              }
                         }
                    }
               }

               // otherwise, insert the object upward if propagation is allowed
               else
               {
                    if(propagate)
                    {
                         if(parent != null)
                         {
                              parent.insert(c, true);
                         }
                    } 
               }
          } 

          // translates all of the objects this node contains by x, y         
          public final void moveAll(double x, double y)
          {
               if(objects == null || objects.isEmpty()) return;
               
 			int i;
               Actor2D a;
               for(i = 0; i < objects.size(); i++)
               {
                    a = (Actor2D) objects.get(i);
                    a.moveBy(x, y);
               }
          }


          public void update(Rectangle2D viewable, LinkedList<Moveable> paintList)
          {
          	int i;
          	
               if(objects == null || objects.isEmpty())
               {
               		return;
               	}
			
			int size = objects.size();
			
			//System.out.println("QuadNode Update");
               // update the list, then remove objects that are no longer in this node
               
               Moveable m;
               
               for(i = 0; i < size; i++)
               {
                    m = (Moveable)objects.get(i);
                    
                    m.update();
                    
                    
                    // ADDED: test if the object is in view
                    // needs to be changed cause this will probably use alot of 
                    // cpu power to process all objects 
                    if(viewable.contains(m.getBounds()) && viewable.intersects(m.getBounds()))
                    {
                    	paintList.add(objects.get(i));
                    }

                    // test if the object left the node; if so, insert upward
                    if(!bounds.contains(m.getBounds()) && !bounds.intersects(m.getBounds())) // might propagate upward
                    {
                         insert((Moveable)objects.remove(i), true);
                    }
                  
               }
               

               // get the updated size since some objects may have been removed
               size = objects.size();

               // test each object for collision against each other object in this node
               for(i = 0; i < size/*-1*/; i++)
               {
                    Moveable a = (Moveable)objects.get(i);

                    for(int j = i+1; j < size; j++)
                    { 
                         Moveable b = (Moveable)objects.get(j);

                         if(a.collidesWith(b))
                         {
                         	//System.out.println("*** Collision Detected ***");
                              a.addCollision(b);
                              b.addCollision(a);
                         }
                         
                         b = null;
                    }
                    
                    a = null;
               }
               	
             	m = null;
          }


          public void paintBounds(Graphics2D g2d, Color c)
          {
               if(c == null) c = Color.red;
               g2d.setPaint(c);
               
               g2d.setTransform(new AffineTransform());
               				   
               g2d.translate(0-viewable.getX(), 0-viewable.getY());
               
               g2d.draw(bounds);
               
          }
          
          
          public  void paint(Graphics2D g)
          {
          	int i;
          	
          	int objectSize = objects.size();
          	
          	Actor2D tempActor;
          	
          	for(i=0; i<objectSize; i++)
          	{
          		tempActor = (Actor2D) objects.get(i);
          		tempActor.paint(g);
          	}
          	
          	tempActor = null;
          }

     }    // QuadNode